/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 // 前序遍历
 // 中 左 右
 // 右 左 中
func preorderTraversal(root *TreeNode) []int {
    res := []int{}
    // nil的情况直接返回
    if root == nil {
        return res
    }
    // 初始化栈
    st := list.New()
    st.PushBack(root)

    for st.Len() > 0 {
        e := st.Remove(st.Back())
        // 遇到nil放入结果集
        if e == nil {
            node := st.Remove(st.Back()).(*TreeNode)
            res = append(res, node.Val)
            continue
        }

        // 获取节点
        node := e.(*TreeNode)
        // 右入栈
        if node.Right != nil {
            st.PushBack(node.Right)
        }

        // 左入栈
        if node.Left != nil {
            st.PushBack(node.Left)
        }

        // 中间入栈并且放入nil标记位
        st.PushBack(node)
        st.PushBack(nil)
    }
    return res
}